package com.fe.class02;

/**
 * @Description 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
 * @Author sosuke :-)
 * @Date 2021/12/3 06:40
 */
public class Code04_EvenTimesOddTimes {
    /**
     * arr中，有两种数，出现奇数次，找到并打印这种数
     * 思路：将问题转化成只有一种数出现奇数次，则需要把当前所有数分成两拨，分别包含这两种数
     * @param arr
     */
    public static void printOddTimesNum(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor = eor ^ arr[i];
        }
        // 假设a和b都出现来奇数次，则此时 eor = a ^ b，且a != b，所以 eor != 0
        System.out.println("eor = a ^ b = " + eor);
        /**
         * eor :     00110010110111000
         * rightOne :00000000000001000
         * 提取出eor最右侧的1，假设eor第n位为1，则说明 a和b 的第n位必不相同，假设 a的第n位为1，则 b的第n位为0
         */
        int rightOne = eor & -eor;

        int onlyOne = 0;
        for (int i = 0; i < arr.length; i++) {
            // 这里根据第n位是否为0将剩下的数分成了两拨，异或上这些第n位为0的数，最终结果就是b
            if ((rightOne & arr[i]) == 0) { // 结果等于0表示arr[i]这个数第n位为0
                onlyOne = onlyOne ^ arr[i];
            }
        }

        System.out.println("b = " + onlyOne + "，a = " + (eor ^ onlyOne));
    }

    public static void main(String[] args) {
        int[] arr2 = {4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4};
        printOddTimesNum(arr2);
    }
}
